#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include "BinaryTree.h"


struct BinaryTreeNode
{
    ElementType data;
    BTNode *left;//左孩子
    BTNode *right;//右孩子
    BTNode *parent;//双亲节点指针
};

BTNode *CreateBTNode(ElementType element)
{
    BTNode *newNode = (BTNode*)malloc(sizeof(BTNode));
    if(newNode == NULL)
    {
        printf("create node malloc error!\n");
        return NULL;
    }

    newNode->data = element;
    newNode->left = newNode->right = newNode->parent = NULL;
    return newNode;
}

ElementType GetNodeData(BTNode *node)
{
    if(node == NULL)
    {
        printf("此节点不存在！\n");
        return NULL;
    }
        
    return node->data;
}

void InsertNode(BTNode *node, ElementType element, int (*funcPtr)(ElementType,ElementType))
{
    if(node == NULL)
    return;

    //元素比节点小
    if(funcPtr(node->data,element) > 0  && node->left == NULL)
    {
        node->left = CreateBTNode(element);
        if(node->left == NULL)
            return;
        
        node->left->parent = node;
        return;
    }
    //元素比节点大
    if(funcPtr(node->data, element) < 0 && node->right == NULL)
    {
        node->right = CreateBTNode(element);
        if(node->right == NULL) 
            return;

        node->right->parent = node;
        return;
    }
    if(funcPtr(node->data, element) == 0)
        return;

    if(funcPtr(node->data, element) > 0)
        InsertNode(node->left ,element,funcPtr);
    else
        InsertNode(node->right,element,funcPtr);
}

struct BinarySortTree
{
    BTNode *root;
};

BSTree *InitBSTree()
{
    BSTree *tree = (BSTree*)malloc(sizeof(BSTree));
    if(tree == NULL)
    {
        printf("init tree malloc error!\n");
        return NULL;
    }

    //二叉树可以空
    tree->root = NULL;
    return tree;
}

void InsertElement(BSTree *tree, ElementType element, int (*funcPtr)(ElementType,ElementType))
{
    //树为空
    if(tree->root == NULL)
        tree->root = CreateBTNode(element);
    else
    //树不为空
        InsertNode(tree->root,element,funcPtr);
}


void TravelNodePrev(BTNode *node,void (*funcPtr)(ElementType))
{
    if(node == NULL)
        return;
    
    funcPtr(node->data);
    TravelNodePrev(node->left,funcPtr);
    TravelNodePrev(node->right,funcPtr);
}
void TravelPrev(BSTree *tree,void (*funcPtr)(ElementType))
{
    TravelNodePrev(tree->root,funcPtr);
}

void TravelNodeMid(BTNode *node, void (*funcPtr)(ElementType))
{
    if(node == NULL)
        return;
    
    TravelNodeMid(node->left,funcPtr);
    funcPtr(node->data);
    TravelNodeMid(node->right, funcPtr);
}
void TravelMid(BSTree *tree, void (*funcPtr)(ElementType))
{
    TravelNodeMid(tree->root,funcPtr);
}

void TravelNodePost(BTNode *node,void (*funcPtr)(ElementType))
{
    if(node == NULL)
        return;
    
    TravelNodePost(node->left,funcPtr);
    TravelNodePost(node->right,funcPtr);
    funcPtr(node->data); 
}
void TravelPost(BSTree *tree,void (*funcPtr)(ElementType))
{
    TravelNodePost(tree->root,funcPtr);
}

BTNode *FindNode(BTNode *node, ElementType element, int (*funcPtr)(ElementType,ElementType))
{
    if(node == NULL)
        return NULL;

    if(funcPtr(node->data, element) == 0)
        return node;
    else if(funcPtr(node->data, element) > 0)
        return FindNode(node->left,element,funcPtr);
    else
        return FindNode(node->right,element,funcPtr);
}
BTNode *FindByElement(BSTree *tree, ElementType element, int (*funcPtr)(ElementType,ElementType))
{
    return FindNode(tree->root,element,funcPtr);
}

bool IsLeftChild(BTNode *parent, BTNode *child)
{
    if(parent->left == child)
        return true;
    else
        return false;
}

void RemoveByElement(BSTree *tree,ElementType element, int (*funcPtr)(ElementType,ElementType))
{
    BTNode *node = FindByElement(tree, element, funcPtr);

    if(node == NULL)
        return;
        
    //该节点为叶子节点
    if(node->left == NULL && node->right == NULL)
    {
        //是根节点的情况,即只有一个root节点
        if(node->parent == NULL)
        {
            free(node);
            tree->root == NULL;
            return;
        }

        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = NULL;
        else
            node->parent->right = NULL;
        
        free(node);
    }
    //左孩子不空，右孩子空
    else if(node->right == NULL)
    {
        //node为根节点
        node->left->parent = node->parent;
        if(node->parent == NULL)
        {
            tree->root = node->left;
            free(node);
            return;
        }

        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = node->left;
        else
            node->parent->right = node->left;
        free(node);
    }
    //左孩子空，右孩子不空
    else if(node->left == NULL)
    {
        node->right->parent = node->parent;
        if(node->parent == NULL)
        {
            tree->root = node->right;
            free(node);
            return;
        }

        if(IsLeftChild(node->parent,node) == true)
            node->parent->left = node->right;
        else
            node->parent->right = node->right;
        free(node);
    }
    //左右孩子都在
    else
    {
        //找右边子树最小的点
        BTNode *MinNode = node->right;
        while(MinNode->left != NULL)
        {
            MinNode = MinNode->left;
        }
        node->data = MinNode->data;

        //如果右边子树最小节点碰巧就是右孩子
        if(MinNode->parent == node)
            node->right = MinNode->right;
        else
            MinNode->parent->left = MinNode->right;
        free(MinNode);
 
    }
}

int GetNumber(BTNode *node)
{
    if(node == NULL)
        return 0;
    
    //节点数量 = 左子树节点个数 + 右子树节点个数 + 1;
    return GetNumber(node->left) + GetNumber(node->right) + 1;
}
int GetNodeNumber(BSTree *tree)
{
    return GetNumber(tree->root);
}
